#希尔排序

#固定步长，delta<=len(List)**0.5
def ShellSort(List, delta):
    gap = len(List) // delta
    while gap > 0:
        for start in range(gap):
            for i in range(start+gap, len(List), gap):
                temp = List[i]
                j = i
                while j >= gap and List[j-gap] > temp:
                    List[j] = List[j-gap]
                    j -= gap
                List[j] = temp
        gap //= delta

a=[7,8,6,9,5,3,0,3]
ShellSort(a, 2)
print(a)


# Sedgewick提出的gaps(n)步长函数。
def gaps(n):
    '''从小到大生成 [1, 5, 19, 41, 109, 209, 505, 929 ...]'''
    i = 0
    while True:
        gap1 = 9 * (4 ** i - 2 ** i) + 1              # 1, 19, 109, 505, 2161 ...
        gap2 = 2 ** (i + 2) * (2 ** (i + 2) - 3) + 1  # 5, 41, 209, 929, 3905 ...
        if n > gap2:  
            yield gap1
            yield gap2
            i += 1
        elif gap2 > n > gap1: 
            yield gap1
            i += 1
        else:
            break

def SedgewickShellSort(List):
    l=len(List)
    if l <= 1: return
    gapl=list(gaps(l))
    for gap in gapl[::-1]: #[..., 41, 19, 5, 1]
        for i in range(gap, l):
            temp = List[i]
            j = i
            while j >= gap and List[j-gap] > temp:
                List[j] = List[j-gap]
                j -= gap
            List[j] = temp





